package cn.edu.bjut.my.thinkinjava._20200501_02_DynamicProgram;

/**
 * 此例测试0-1背包问题
 * <p>
 * 题目：给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。
 * 其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
 * 举个简单的例子，输入如下：
 * N = 3, W = 4
 * wt = [2, 1, 3]
 * val = [4, 2, 3]
 * 算法返回 6，选择前两件物品装进背包，总重量 3 小于 W，可以获得最大价值 6。
 * <p>
 * 动态规划判定：
 * 含有子问题？好像是  bag5=bag3+bag2，bag4=bag3+bag1
 * 子问题重叠？好像是 bag3重叠
 * 状态转移方程？
 * 状态：原问题与子问题变化的量是 背包装载质量、物品个数
 * 选择：每种状态能做出的选择、
 * dp[i][w] 表示：对于前 i 个物品，当前背包的容量为 w 时，这种情况下可以装下的最大价值是 dp[i][w]。
 */
public class _03Knapsack {
    //TODO
    public int knapssack(int W, int N, int[] wt, int[] val) {
        int[][] dp = new int[N + 1][W + 1];
        for (int i = 0; i < N + 1; i++) {
            dp[i][0] = 0;
        }

        for (int j = 0; j < W + 1; j++) {
            dp[0][j] = 0;
        }

        for (int i = 1; i <= N; i++) {
            for (int w = 1; w <= W; w++) {
                if (w - wt[i - 1] < 0) {
                    dp[i][w] = dp[i - 1][w];
                } else {
                    dp[i][w] = Math.max(dp[i - 1][w - wt[i - 1]] + val[i - 1], dp[i - 1][w]);
                }
            }
        }
        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < W + 1; j++) {
                System.out.print(dp[i][j] + "  ");
            }
            System.out.println();
        }
        return 0;
    }

    public static void main(String[] args) {
        int N = 3;
        int W = 4;
        int wt[] = {2, 1, 3};
        int val[] = {4, 2, 3};
        new _03Knapsack().knapssack(W, N, wt, val);
    }
    /**
     *
     */
}
